package demo.linklist;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class NodeUtil {
    public static void main(String[] args) {
        //sNodePrint(reverse(sNodeBuild("1234567")));
        //sNodePrint(sNodeMid(sNodeBuild("1234567")));
        //System.out.println(isHuiWenNode3(sNodeBuild("12345654321")));
        //sNodePrint(merge(sNodeBuild("02468"), sNodeBuild("13579")));
        sNodePrint(reverseKNodes(sNodeBuild("123456789"), 3));
        sNodePrint(reverseKNodes2(sNodeBuild("123456789"), 3));
    }

    /**
     * 将单链表的每K个节点之间逆序 方法2 非栈
     *
     * @param head
     * @param K
     * @return
     */
    public static Node reverseKNodes2(Node head, int K) {
        if (K < 2) {
            return head;
        }
        Node cur = head;
        Node pre = null;
        Node next = null;
        Node start = null;
        int count = 1;
        while (cur != null) {
            next = cur.next;
            if (count == K) {
                start = pre == null ? head : pre.next;
                head = pre == null ? cur : head;
                resign(pre, start, cur, next);
                pre = start;
                count = 0;
            }
            count++;
            cur = next;
        }
        return head;
    }

    public static void resign(Node left, Node start, Node end, Node right) {
        Node pre = start;
        Node cur = start.next;
        Node next = null;
        while (cur != right) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        if (left != null) {
            left.next = end;
        }
        start.next = right;
    }

    /**
     * 将单链表的每K个节点之间逆序 方法1 栈
     *
     * @param head
     * @param K
     * @return
     */
    public static Node reverseKNodes(Node head, int K) {
        if (K < 2) {
            return head;
        }
        Stack<Node> stack = new Stack<Node>();
        Node newHead = head;
        Node cur = head;
        Node pre = null;
        Node next = null;
        while (cur != null) {
            stack.push(cur);
            next = cur.next;
            if (stack.size() == K) {
                pre = resign(stack, pre, next);
                newHead = newHead == head ? cur : newHead;
            }
            cur = next;
        }
        return newHead;
    }

    public static Node resign(Stack<Node> stack, Node left, Node right) {
        Node cur = stack.pop();

        if (left != null) {
            left.next = cur;
        }

        Node next = null;
        while (!stack.isEmpty()) {
            next = stack.pop();
            cur.next = next;
            cur = next;
        }
        cur.next = right;
        return cur;
    }

    /**
     * 合并链表
     *
     * @param head1
     * @param head2
     * @return
     */
    public static Node merge(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return head1 != null ? head1 : head2;
        }

        Node head = head1.val < head2.val ? head1 : head2;
        Node cur1 = head == head1 ? head1 : head2;
        Node cur2 = head == head1 ? head2 : head1;
        Node pre = null;
        Node next = null;
        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                pre = cur1;
                cur1 = cur1.next;
            } else {
                next = cur2.next;
                pre.next = cur2;
                cur2.next = cur1;
                pre = cur2;
                cur2 = next;
            }
        }
        pre.next = cur1 == null ? cur2 : cur1;
        return head;
    }

    /**
     * 判断是否是回文结构 --栈
     * @param head
     * @return
     */
    public static boolean isHuiWenNode1(Node head) {
        Node tmpHead = head;
        Stack<Node> stack = new Stack<Node>();
        while (tmpHead != null) {
            stack.push(tmpHead);
            tmpHead = tmpHead.next;
        }

        while (head != null) {
            if (head.val != stack.pop().val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    /**
     * 判断是否是回文结构--栈
     * @param head
     * @return
     */
    public static boolean isHuiWenNode2(Node head) {
        Node tmpHead = sNodeMid(head);
        Stack<Node> stack = new Stack<Node>();
        while (tmpHead != null) {
            stack.push(tmpHead);
            tmpHead = tmpHead.next;
        }

        while (stack.size() > 0) {
            if (head.val != stack.pop().val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    /**
     * 判断是否是回文结构--非栈
     * @param head
     * @return
     */
    public static boolean isHuiWenNode3(Node head) {
        Node tmpHead = head;
        tmpHead = sNodeMid(tmpHead);
        tmpHead = reverse(tmpHead);

        while (tmpHead != null) {
            if (head.val != tmpHead.val) {
                return false;
            }
            head = head.next;
            tmpHead = tmpHead.next;
        }
        return true;
    }

    /**
     * 构建数据
     *
     * @param strParam
     * @return
     */
    public static Node sNodeBuild(String strParam) {
        List<Node> list = new ArrayList<Node>();
        String[] strArr = strParam.split("");
        for (String str : strArr) {
            list.add(new Node(Integer.parseInt(str)));
        }

        for (int i = 0; i < list.size() - 1; i++) {
            Node pre = list.get(i);
            Node next = list.get(i + 1);
            pre.next = next;
        }
        return list.get(0);
    }

    /**
     * 打印链表
     *
     * @param head
     */
    public static void sNodePrint(Node head) {
        List<Node> list = new ArrayList<Node>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }

        for (Node sNode : list) {
            if (sNode.next != null) {
                System.out.print(sNode.val + "->");
            } else {
                System.out.print(sNode.val);
            }
        }
        System.out.println();
    }

    /**
     * 采用快慢指针处理
     *
     * @param head
     * @return
     */
    public static Node sNodeMid(Node head) {
        if (head == null) {
            return null;
        }
        Node fast = head;
        Node slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 逆序链表
     * @param head
     * @return
     */
    public static Node reverse(Node head) {
        Node pre = null;
        while (head != null) {
            Node next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    private static class Node {
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return val + "";
        }
    }

}
